package com.yang.Tree;

import java.util.ArrayList;

/**
 * @Author: yang
 * @Description:  二叉搜索树系列题
 * @Date: Created in 20:27 2022/8/4
 * @Modified By:
 */
public class BSearchT {
}



class Solution {
    public class TreeNode3 {
        int val;
        TreeNode3 left;
        TreeNode3 right;

        TreeNode3() {
        }

        TreeNode3(int val) {
            this.val = val;
        }

        TreeNode3(int val, TreeNode3 left, TreeNode3 right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /*给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
    有效 二叉搜索树定义如下：
    节点的左子树只包含 小于 当前节点的数。
    节点的右子树只包含 大于 当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。*/
    // 因为二叉搜索树的特殊性质， 中序遍历就是从小到大了 所以如果有不满足的  那就false
    // 使用Long.MIN_VALUE是因为测试用例中存在 最小int值无法判断
    private long preValue = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode3 root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        // 根据二叉搜索树性质与中序遍历  应该是从小到大的遍历顺序
        if (root.val <= preValue) {
            return false;
        }
        preValue = root.val;
        return isValidBST(root.right);
    }

    /*给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
    你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。
    如果节点不存在，则返回 null 。*/
    public TreeNode3 searchBST(TreeNode3 root, int val) {
        if(root == null) return null;

        if(root.val == val){
            return root;
        }else if(root.val > val){
            return searchBST(root.left, val);
        }else{
            return searchBST(root.right, val);
        }
    }

/*给你一个二叉搜索树的根节点root,返回树中任意两不同节点值之间的最小差值
差值是一个正数，其数值等于两值之差的绝对值。*/

    // 利用二叉搜索树的有序性 把它当做一个有序数组进行处理 需要一个指针保存前一个指针
    int minValue = Integer.MAX_VALUE;
    TreeNode3 pre;
    public int getMinimumDifference(TreeNode3 root) {
        getMinimun(root);
        return minValue;
    }
    private void getMinimun(TreeNode3 cur){
        if(cur == null){
            return;
        }
        getMinimun(cur.left);
        if(pre != null){
            if(minValue > cur.val - pre.val){
                minValue = cur.val - pre.val;
            }
        }
        pre = cur;
        getMinimun(cur.right);
        return;
    }


    /*给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
    如果树中有不止一个众数，可以按 任意顺序 返回。
    假定 BST 满足如下定义：
    结点左子树中所含节点的值 小于等于 当前节点的值
    结点右子树中所含节点的值 大于等于 当前节点的值
    左子树和右子树都是二叉搜索树 */

    // TODO: 2022/8/5  这个是二叉搜索树的 如果不是二叉搜索树呢？
    /*如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。*/
    // 因为有可能不止一个众数
    // 我们可以比较如果当前数比上一个数相等 count++
    // 否则就让count = 1（更新）
    // 如果再次遇到等于maxCount的 就把他加入结果集
    // 但是无法确定当前maxCount是不是最大的  所以 如果后面遇到了大于maxCount的数 我们就清空结果集
    int maxCount = 0;
    int count = 0;
    // ArrayList有clear方法
    ArrayList<Integer> resList;
    public int[] findMode(TreeNode3 root) {
        resList = new ArrayList<>();
        getMode(root);
        int[] res = new int[resList.size()];
        for(int i = 0; i < resList.size(); i++){
            res[i] = resList.get(i);
        }
        return res;
    }
    private void getMode(TreeNode3 cur){
        if(cur == null){
            return;
        }
        getMode(cur.left);
        // 是第一个节点
        if(pre == null){
            count = 1;
        }else if(cur.val == pre.val){
            count ++;
            // 新数
        }else {
            count = 1;
        }
        // 相等说明出现了另一个众数
        if(count == maxCount){
            resList.add(cur.val);
        }
        // 大于说明之前找到的不是众数 需要clear
        if(count > maxCount){
            maxCount = count;
            resList.clear();
            resList.add(cur.val);
        }
        pre = cur;
        getMode(cur.right);
    }
}
